1. Field of the Invention
The present invention relates to decoding of a variable length code, such as a Huffman code, and more particularly to a scheme for variable length decoding in a computer system using lookup tables.
2. Related Art
The recent development of computer-based applications such as video telephony, video conferencing and multimedia has lead to the development of compression techniques for video data in computer systems. These compression techniques reduce the amount of data required to represent moving images and corresponding sound to a manageable quantity. This facilitates transmission of video data over communication networks as well as the storage of video data in data storage devices for later retrieval.
To this end standards have been developed to specify how video data is compressed. One of these standards is the Motion Picture Experts Group (MPEG) standard. The MPEG standard specifies a compressed format for motion picture video and associated sound in order to facilitate transmission of video images at rates up to 30 frames per second. The MPEG standard additionally provides other features, such as single frame advance, reverse motion and still frame video.
Under the MPEG standard, an image is encoded by breaking the image into distinct areas, sampling data from these areas, and representing each area in coded form. This data is coded by a transmitting device and decoded by a receiving device in order to facilitate transmission of full motion video across a communication network. Alternatively, coded video data may be stored in a computer system main memory or in a non-volatile storage device, such as a disk drive, for later viewing.
Under standards such as MPEG, video data is compressed by exploiting statistical redundancies in the video data. The MPEG standard encodes video data using a variant of Huffman coding, which is a "variable length" coding scheme. Variable length coding schemes convert symbols (from a stream of symbols such as a video stream) into variable length codewords, wherein each symbol is associated with a unique codeword. These codewords are assigned to symbols so that more commonly occurring symbols are assigned to shorter codewords, and less commonly occurring symbols are assigned to longer codewords. If done properly, this can minimize the amount of encoded data required to represent a stream of symbols.
In order to decode a variable length codeword, some existing systems parse the bitstream containing the codeword using a binary tree. This technique is very slow. Other systems use a single lookup table of symbols for all possible codewords. The problem with such a lookup table is that it must be large enough to accommodate the largest possible codeword. Under the MPEG-II standard, codewords can be as large as 17 bits in size, necessitating a table of size 2.sup.17 =131,072 entries. Tables of this size can be prohibitively expensive to implement because they consume a large amount of memory, and prohibitively slow, because larger memories require longer access times. Note that decoding speed can be a critical bottleneck for applications such as video conferencing and MPEG playback, which may require up to 30 frames per second of data.
A scheme that uses multiple lookup tables is described in U.S. Pat. No. 5,253,053, entitled "Variable Length Decoding Using Lookup Tables," to inventors Chu, et al. This patent discloses a scheme that uses two smaller lookup tables to decode a variable length codeword. A first table, called a "frequent" table, is used to decode frequently occurring smaller codewords. A second table, called an "infrequent" table, is used to decode less frequently occurring longer codewords.
Although the scheme proposed in the above patent reduces memory requirements for the lookup tables, it suffers from a number of drawbacks. First, the schemes does not take advantage of the possibility of performing multiple table lookups in parallel, which can increase performance. Second, variable length codewords are typically not matched to the lookup table size. Consequently, after a lookup is performed, the remaining bits in the input stream must often be realigned. This realignment process can be a time-consuming. Third, the two stage lookup process disclosed in the above patent does not disclose the possibility of selecting different secondary lookup tables based upon which prefix value was inputted into the primary lookup table. This selection of different secondary lookup tables allows more general types of variable length codes to be decoded.